package main.leetcode.offer.firstround.from51to68;

import main.datastruc.ListNode;

/**
 * 52.两个链表的第一个公共节点
 *
 * <p>输入两个链表，找出它们的第一个公共节点。
 *
 * <p>注意：如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex52 {
    public static void main(String[] args) {
        //
    }

    //    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //        ListNode preA = headA, preB = headB;
    //        int n1 = 0, n2 = 0;
    //        while (preA != null) {
    //            ++n1;
    //            preA = preA.next;
    //        }
    //        while (preB != null) {
    //            ++n2;
    //            preB = preB.next;
    //        }
    //
    //        preA = headA;
    //        preB = headB;
    //
    //        if (n1 > n2) {
    //            for (int i = 0; i < n1 - n2; i++) {
    //                preA = preA.next;
    //            }
    //        } else if (n2 > n1) {
    //            for (int i = 0; i < n2 - n1; i++) {
    //                preB = preB.next;
    //            }
    //        }
    //
    //        while (preA != preB) {
    //            preA = preA.next;
    //            preB = preB.next;
    //        }
    //
    //        return preA;
    //    }

    // A路段 + 公共路段 + B路段 = B路段 + 公共路段 + A路段
    // A [1,3,5,7,9,11]
    // B     [2,4,9,11]
    //
    // A 1-3-5-7 + 9-11 + 2-4   到达9
    // B 2-4 + 9-11 + 1-3-5-7   到达9
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode preA = headA, preB = headB;
        while (preA != preB) {
            preA = preA == null ? headB : preA.next;
            preB = preB == null ? headA : preB.next;
        }
        return preA;
    }
}
